package atpa.partial;

import java.util.StringTokenizer;

public class ATPAPartial {

    public void Josephus(int noduri, int deleteEvery) {
        Nod t = new Nod(1);
        Nod x = t;
        for (int i = 2; i <= noduri; i++) {
            x.urm = new Nod(i);
            x = x.urm;
        }
        x.urm = t;
        x = t;
        while (x != x.urm) {
            for (int i = 1; i < deleteEvery - 1; i++) {
                x = x.urm;
            }
            x.urm = x.urm.urm;
            x = x.urm;
        }
        System.out.println("Valoarea = " + x.val);
    }

    public void Eratostene(int N) {
        boolean[] a = new boolean[N];
        for (int i = 2; i < N; i++) {
            a[i] = true;
        }
        for (int i = 2; i < N; i++) {
            if (a[i] != false) {
                for (int j = i; j * i < N; j++) {
                    a[j * i] = false;
                }
            }
        }
        for (int i = 2; i < N; i++) {
            if (a[i] == true) {
                System.out.println(i);
            }
        }
    }

    public void expresie(String expr) {
        char[] vect = expr.toCharArray();
        System.out.println(vect);
        StivaL s = new StivaL(vect.length);
        for (int i = 0; i < vect.length; i++) {
            System.out.print("char = " + vect[i]);
            if (vect[i] == '{' || vect[i] == '[' || vect[i] == '(') {
                s.push(vect[i]);
                System.out.print(" l-am bagat in stiva ");
            } else if (vect[i] == '}' || vect[i] == ']' || vect[i] == ')') {
                System.out.print(" compar, e egal cu },],) ");
                if (vect[i] == '}' && s.peek() == '{') {
                    s.pop();
                    System.out.print(" l-am scos din stiva ");
                    continue;
                } else if (vect[i] == ']' && s.peek() == '[') {
                    s.pop();
                    System.out.print(" l-am scos din stiva ");
                    continue;
                } else if (vect[i] == ')' && s.peek() == '(') {
                    s.pop();
                    System.out.print(" l-am scos din stiva ");
                    continue;
                } else {
                    System.out.println("\n***Eroare element: " + vect[i] + ", pozitia=" + i + "***");
                }

            }
            System.out.println("");
        }
        if (!s.isEmpty()) {
            System.out.println("Eroare la primul element !!!");
        }
    }

    public void selectionSort(int[] x) {
        for (int i = 0; i < x.length - 1; i++) {
            for (int j = i + 1; j < x.length; j++) {
                if (x[i] > x[j]) {
                    int temp = x[i];
                    x[i] = x[j];
                    x[j] = temp;
                }
            }
        }
        for (int i = 0; i < x.length; i++) {
            System.out.println(x[i] + " ");
        }
    }

    public void insertionSort(int[] tab) {
        int tmp, j;
        for (int i = 0; i < tab.length; i++) {
            tmp = tab[i];
            j = i;
            while (j > 0 && tmp < tab[j - 1]) {
                tab[j] = tab[j - 1];
                j--;
            }
            tab[j] = tmp;
        }
        for (int i = 0; i < tab.length; i++) {
            System.out.println(tab[i]);
        }
    }

    public void bubbleSort(int[] vect) {
        boolean gasit = true;
        int aux = 0;
//        long start = System.currentTimeMillis();
        while (gasit) {
            gasit = false;
            for (int i = 0; i < vect.length - 1; i++) {
                if (vect[i] > vect[i + 1]) {
                    aux = vect[i];
                    vect[i] = vect[i + 1];
                    vect[i + 1] = aux;
                    gasit = true;
                }
            }
        }
//        long end = System.currentTimeMillis();
//        return Arrays.toString(vect);
        for (int i = 0; i < vect.length - 1; i++) {
            System.out.println(vect[i]);
        }
    }

    public void sumaMax(int[] tab) {
        ListaDbl l = new ListaDbl(tab.length, tab);
        Nod x = l.t;
        Nod start = x;
        Nod fin = x;
        Nod y = null;
        int st = 0;
        int smax = 0;
        while (x != null) {
            System.out.println("while 1");
            st = 0;
            y = x;
            while (y != null) {
                System.out.println("while 2");
                st += y.val;
                if (st > smax) {
                    System.out.println("if 1");
                    start = x;
                    fin = y;
                    smax = st;
                }
                y = y.urm;
            }
            x = x.urm;
        }
        System.out.println("Start = " + start.val);
        System.out.println("Fin = " + fin.val);
        System.out.println("smax = " + smax);
    }

    public void subSir(String in) {
        StringTokenizer st = new StringTokenizer(in, "#");
        char[] secv = st.nextToken().toCharArray();
        char[] sub = st.nextToken().toCharArray();
        ListaDbTemp Secv = new ListaDbTemp(secv.length, secv);
        ListaDbTemp Sub = new ListaDbTemp(sub.length, sub);
        Nod x = Secv.t;
        Nod y = Sub.t;
        Nod a = x;
        boolean subsir = false;
        while (x != null) {
            a = x;
            if (x.val == y.val) {
                while (y != null && x != null) {
                    if (x.val == y.val) {
                        subsir = true;
                        if (x.urm == null && y.urm != null) {
                            subsir = false;
                            break;
                        }
                        x = x.urm;
                        y = y.urm;
                    } else {
                        subsir = false;
                        break;
                    }
                }
            }
            x = a;
            x = x.urm;
            y = Sub.t;
        }
        if (subsir) {
            System.out.println("secventa este subsir");
        } else {
            System.out.println("secv NU este subsir");
        }


    }

    public void subSir2(String input) {
        String[] stgdrp = input.split("#");
        char[] stg = stgdrp[0].toCharArray();
        char[] drp = stgdrp[1].toCharArray();
        ListaDbTemp l1 = new ListaDbTemp(stg.length, stg);
        ListaDbTemp l2 = new ListaDbTemp(drp.length, drp);
        Nod x = l1.t;
        Nod y = l2.t;
        Nod a = x;
        boolean gasit_litera = false;
        while (x != null) {
            while (y != null) {
                if (a.val == y.val) {
                    if (a.urm == null && y.urm != null) {
                        gasit_litera = false;
                        break;
                    }
                    a = a.urm;
                    y = y.urm;
                    gasit_litera = true;
                } else {
                    gasit_litera = false;
                    break;
                }
            }
            if (gasit_litera) {
                break;
            }
            x = x.urm;
            a = x;
            y = l2.t;
        }
        if (!gasit_litera) {
            System.out.println("negasit");
        }
    }

    public void insertieStiva(int[] tab) {
        StivaL s1 = new StivaL(tab.length);
        StivaL s2 = new StivaL(tab.length);
        for (int i = 0; i < tab.length; i++) {
            if (s1.isEmpty() || tab[i] > s1.peek()) {
                s1.push(tab[i]);
            } else {

                while (tab[i] < s1.peek()) {
                    s2.push(s1.pop());
                }
                s1.push(tab[i]);
                while (!s2.isEmpty()) {
                    s1.push(s2.pop());
                }
            }
        }
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        s2.show();



    }

    public void duplicate(int[] tab) {
        ListaDbl l = new ListaDbl(tab.length, tab);
        Nod x = l.t;
        Nod a = x.urm;
        while (x != null) {
            a = x.urm;
            while (a != null) {
                if (a.val == x.val) {
                    a.ant.urm = a.urm;
                    if (a.urm != null) {
                        a.urm.ant = a.ant;
                    }
                }
                a = a.urm;
            }
            x = x.urm;
        }
        l.show();
    }

    public void duplicate2(int[] tab) {
        ListaDbl ls = new ListaDbl(tab.length, tab);
        Nod x = ls.t;
        Nod y = x;
        while (x.urm != null) {
            y = x.urm;
            while (y != null) {
                if (x.val == y.val) {
                    y.ant.urm = y.urm;
                    if (y.urm != null) {
                        y.urm.ant = y.ant;
                    }
                }
                y = y.urm;
            }
            x = x.urm;
        }
        ls.show();
    }

    public void cautareBinara(String secv) {
        StringTokenizer st1 = new StringTokenizer(secv, "#");
        int N = Integer.parseInt(st1.nextToken());
        StringTokenizer st2 = new StringTokenizer(st1.nextToken());
        int[] tab = new int[st2.countTokens()];
        int i = 0;
        while (st2.hasMoreTokens()) {
            tab[i] = Integer.parseInt(st2.nextToken());
            i++;
        }
        ListaDbl l = new ListaDbl(tab.length, tab);
        Nod x = l.t;
        int start = 1;
        int end = l.count() - 1;
        int mid = 0;

        while (start <= end) {
            System.out.println("while 1");
            x = l.t;
            System.out.println("x.val = "+x.val);
            mid = (start + end) / 2;
            System.out.println("start = " + start);
            System.out.println("end = " + end);
            System.out.println("mid = " + mid);
            while (x != null) {
                System.out.println("while 2");
                for (i = 1; i < mid; i++) {
                    System.out.println("for: i = " + i);
                    x = x.urm;
                    System.out.println("x.val = "+x.val);
                }
                if (x.val == N) {
                    System.out.println("gasit pe pozitia " + mid);
                    start=end+1;
                    break;
                } else if (x.val < N) {
                    System.out.println("x.val<n");
                    start = mid + 1;
                    break;
                } else {
                    System.out.println("x.val>n");
                    end = mid - 1;
                    break;
                }
            }

        }
    }
    
    public void cautaBinar(int N, int[] tab){
		int startPos = 0;
		int endPos = tab.length-1;
		int middlePos;
		
		while(startPos <= endPos){
			middlePos = (startPos+endPos)/2;
			System.out.println("...middlePos="+middlePos+" | val="+tab[middlePos]);
			if(tab[middlePos]==N){
				System.out.println("Found N="+N+" | pos="+middlePos);
				endPos-=100;// intrerupe bucla while
			} else if(tab[middlePos] < N){
				startPos = middlePos+1;
				
			} else if(tab[middlePos] > N){
				endPos = middlePos-1;
			}
		}
		
	}

    public static void main(String[] args) {
        ATPAPartial p = new ATPAPartial();
        int[] tab = {1,2,3,4,5,6};
        //p.subSir("11111111#1");
        // p.insertieStiva(tab);
        //p.duplicate(tab);
        p.cautareBinara("1#1 2 3 4 5 6");
       // p.cautaBinar(2, tab);
    }
}